package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author By ZengPeng
 */
public class 力扣_236_二叉树的最近公共祖先 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_236_二叉树的最近公共祖先()
                .lowestCommonAncestor(TreeNode.initRoot(),new TreeNode(6),new TreeNode(8)));
    }

    /**
    题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
     满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

     示例 1：
     输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     输出：3
     解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

     示例 2：
     输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
     输出：5
     解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

     示例 3：
     输入：root = [1,2], p = 1, q = 2
     输出：1

    分析：【PR 💞💞💞💞💞】
       1.深度优先遍历：分别遍历一次，得到根节点到目标节点的所有节点路径Deque ,【回溯将节点添加到队列Deque】
                    再同时遍历两个队列，队列值不同时返回上一个节点
            --执行用时：10 ms, 在所有 Java 提交中击败了14.55%的用户
       大神.深度优先遍历：后续遍历的思想：左右子树的结果汇总给父节点，左为null,返回右节点。右为null,返回左节点。
                    若 root 是 p, q的 最近公共祖先 ，则只可能为以下情况之一：
                     1.p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
                            此时节点left、right都不为null,此节点即是【最近祖节点】，向上级【回溯返回此节点】
                     2.p = root，且 q 在 root 的左或右子树中；q = root，且 p 在 root 的左或右子树中；
                            即：两个节点是直接亲缘关系. 如： q.left = p
                            此时左右节点返回时，left、right只有一个不为null,q 即是【最近祖节点】，向上级【回溯返回此节点】
            --执行用时：6 ms, 在所有 Java 提交中击败了99.99%的用户

    边界值 & 注意点：
       1.
     **/
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //2.后续遍历的思想：左右子树的结果汇总给父节点，左为null,返回右节点。右为null,返回左节点。
        if(root==null || root.val==p.val || root.val==q.val) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if( left== null) return right;
        if(right == null) return left;
        return root;

        // 1.深度优先遍历：分别遍历一次，得到根节点到目标节点的所有节点路径Deque 。
      /*  Deque<TreeNode> dequeP=new ArrayDeque<>();
        getPath(root,p,dequeP);
        Deque<TreeNode> dequeQ=new ArrayDeque<>();
        getPath(root,q,dequeQ);
        while (!dequeP.isEmpty() && !dequeQ.isEmpty()){
            TreeNode peek = dequeP.peek();
            if(dequeP.poll()!=dequeQ.poll())
                return root;
            else
                root = peek;
        }
        return  root;*/
    }
    //深度优先遍历找到从根节点到目标节点路径
    private  boolean getPath(TreeNode root, TreeNode target, Deque<TreeNode> deque) {
        if(root==null) return false;
        if(root.val==target.val || getPath(root.left, target, deque) || getPath(root.right, target, deque)){
            deque.push(root);
            return true;
        }
        return  false;
    }
}
